BZOJ 4033 T1

Description

有一棵点数为 N 的树,树边有边权。给你一个在 0~ N 之内的正整
数 K ,你要在这棵树中选择 K个点,将其染成黑色,并将其他 的
N-K个点染成白色 。 将所有点染色后,你会获得黑点两两之间的距
离加上白点两两之间的距离的和的受益。问受益最大值是多少。

Input

第一行包含两个整数 N, K 。
接下来 N-1 行每行三个正整数 fr, to, dis , 表示该树中存在一条长度
为 dis 的边 (fr, to) 。输入保证所有点之间是联通的。

Output

输出一个正整数,表示收益的最大值。

Sample Input

3 1
1 2 1
1 3 2

Sample Output

3

Solution

题解
说起来我好像是去年看到的这道题了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>

#define maxn 2000+5
#define maxm 4000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v,w;
int next;
}s[maxm];

ll f[maxn][maxn],sup[maxn];
int size[maxn];
int first[maxn],ind;
int n,m;

void insert(int u,int v,int w)
{

s[ind]=(sides){u,v,w,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,w,first[v]},first[v]=ind++;
}

void DP(int x,int p)
{

size[x]=1;
for(int i=first[x];i!=-1;i=s[i].next)
if( s[i].v!=p ){
DP(s[i].v,x),set(sup,0);
for(int j=0;j<=size[x]&&j<=m;j++)
for(int k=0;k<=size[s[i].v]&&k<=m-j;k++){
int b=j+k,w=size[x]+size[s[i].v]-b;
ll cost=j*k+(size[x]-j)*(size[s[i].v]-k)+k*(m-j-k)+(size[s[i].v]-k)*(n-m-size[x]-size[s[i].v]+j+k);
cost=cost*s[i].w;
sup[j+k]=max(sup[j+k],f[x][j]+f[s[i].v][k]+cost);
}
for(int j=0;j<=m;j++) f[x][j]=max(f[x][j],sup[j]);
size[x]+=size[s[i].v];
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("4033.in","r",stdin);
freopen("4033.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
set(first,-1);
for(int i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
}
DP(1,0);
printf("%lld",f[1][m]);
return 0;
}